Mrówka

Limit pamięci: 32 MB

Myśląca bajtocka mrówka chodzi po krawędziach sześcianu ABCDEFGH:

Zastanawia się, na ile sposobów może przejść z zadanego wierzchołka sześcianu do wskazanego innego, przechodząc dokładnie po krawędziach (jeżeli mrówka zaczyna iść po danej krawędzi, to nigdy nie zawróci i kiedyś dojdzie do drugiego jej końca). Jeżeli mrówka przejdzie razy po tej samej krawędzi, to krawędź tą liczymy razy. Mrówka chciałaby, żeby jej trasa była ciekawa, to znaczy, jeżeli w pewnym momencie mrówka wejdzie po pewnej krawędzi do danego wierzchołka, to nie chciałaby wyjść z tego wierzchołka w kolejnym kroku po tej samej krawędzi.

Ponieważ mrówka potrafi jedynie liczyć od do , dla pewnego , to podaj jej tylko resztę z dzielenia przez liczby możliwych tras, spełniających powyższe warunki.

Zadanie

Napisz program który:

• wczyta ze standardowego wejścia początkowy i końcowy wierzchołek na trasie mrówki, liczbę krawędzi do pokonania i liczbę ,
• obliczy resztę z dzielenia przez liczby ciekawych tras mrówki spełniających jej wymagania,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie wielkie litery i (, ), oddzielone pojedynczym odstępem i oznaczające wierzchołki początkowy i końcowy na trasie mrówki. Drugi wiersz wejścia zawiera dwie liczby całkowite i (, ), oddzielone pojedynczym odstępem.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia należy zapisać jedną liczbę całkowitą - resztę z dzielenia przez liczby ciekawych tras mrówki z wierzcholka do wierzchołka , złożonych z dokładnie krawędzi sześcianu.

Przykład

A B
3 100

2

Autor zadania: Jakub Radoszewski.